package leetcode.N201_N300;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/19 11:43 上午
 */
public class N283 {

    public void moveZeroes(int[] nums) {
        int unZeroIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i];
            if (currentNum == 0) {
                int index = findNextUnZeroIndex(unZeroIndex, i, nums);
                if (index == -1) {
                    // 后续已经没有非0数字 也就是所有的0都已经移动到数组的末尾了
                    return;
                }
                // 交换当前数和0的位置
                nums[i] = nums[index];
                nums[index] = 0;
                // index的位置已经设置成0了  所以最近也要index + 1的位置是非零数
                unZeroIndex = index + 1;
            }
        }
    }

    private int findNextUnZeroIndex(int unZeroIndex, int zeroIndex, int[] nums) {
        int start = Math.max(unZeroIndex, zeroIndex + 1);
        for (int i = start; i < nums.length; i++) {
            if (nums[i] != 0) {
                return i;
            }
        }
        // 没有非0数了
        return -1;
    }
}
